Перевод: с русского на все языки

со всех языков на русский

Задача О Назначениях

  • 1 задача о назначениях

    1. assignment problem

     

    задача о назначениях
    Вид задачи линейного программирования, с помощью которой решаются вопросы типа: как распределить рабочих по станкам, чтобы общая выработка была наибольшей или затраты на заработную плату наименьшими (поскольку для каждой комбинации «рабочий — станок» характерна своя производительность труда), как наилучшим образом распределить экипажи самолетов, как назначить людей на различные должности (отсюда и название задачи) и т.д. Математически такие задачи — частный случай распределительных задач с той особенностью, что в них объемы наличных и требующихся для выполнения каждой работы ресурсов равны единице, т.е. aj = bj = 1, и все xij=1, если работник i назначен на работу j, или нулю в остальных случаях (обозначения см. в статье Распределительные задачи). Иначе говоря, для выполнения каждой работы расходуется только один вид ресурса, а каждый ресурс может быть использован на одной работе: ресурсы неделимы между работами, а работы — между ресурсами. Исходные данные группируются в таблице, которая называется «матрицей оценок», результаты — в «матрице назначений«. Количество возможных вариантов назначений равно факториалу числа работ и ресурсов и огромно даже в небольшой задаче. Поэтому для нахождения оптимального варианта применяют специальные алгоритмы. Среди них особенно эффективен при решении задачи вручную так называемый венгерский метод.
    [ http://slovar-lopatnikov.ru/]

    Тематики

    EN

    Русско-английский словарь нормативно-технической терминологии > задача о назначениях

  • 2 задача о назначениях

    Русско-белорусский математический словарь > задача о назначениях

  • 3 задача о назначениях

    Русско-английский технический словарь > задача о назначениях

  • 4 задача о назначениях

    1) Mathematics: problem of allocation
    2) Economy: assignment problem

    Универсальный русско-английский словарь > задача о назначениях

  • 5 задача о назначениях

    n

    Универсальный русско-немецкий словарь > задача о назначениях

  • 6 задача о назначениях

    Русско-немецкий финансово-экономическому словарь > задача о назначениях

  • 7 задача о назначениях

    assignment problem, problem of allocation

    Русско-английский словарь по электронике > задача о назначениях

  • 8 задача о назначениях

    problem of allocation, assignment problem

    Русско-английский словарь по радиоэлектронике > задача о назначениях

  • 9 задача о назначениях

    Русско-казахский экономический словарь > задача о назначениях

  • 10 задача о назначениях

    Русско-английский словарь по вычислительной технике и программированию > задача о назначениях

  • 11 задача о назначениях

    assignment problem мат., problem of allocation

    Русско-английский научно-технический словарь Масловского > задача о назначениях

  • 12 задача о назначениях на должность

    Универсальный русско-английский словарь > задача о назначениях на должность

  • 13 квадратичная задача о назначениях

    Information technology: quadratic assignment problem

    Универсальный русско-английский словарь > квадратичная задача о назначениях

  • 14 задача

    1) exercise

    2) problem
    3) sum
    4) task
    – бухгалтерская задача
    – граничная задача
    – дополнительная задача
    – задача граничная
    – задача Дирихле
    – задача контрольная
    – задача Коши
    – задача о брахистохроне
    – задача о выборе
    – задача о диете
    – задача о назначениях
    – задача о поставщике
    – задача о размещении
    – задача о рекламе
    – задача о сделке
    – задача о столкновениях
    – задача обороны
    – задача Плато
    – задача регулирования
    – задача складирования
    – задача торга
    – контрольная задача
    – краевая задача
    – нестанционарная задача
    – обратная задача
    – поставленная задача
    – прикладная задача
    – прямая задача
    – разрешимая задача
    – текущая задача
    – транспортная задача
    – экстремальная задача

    задача в линиях обслуживания — queueing problem


    задача двух тел — two-body problem


    задача многих тел — <astr.> many-body problem


    задача на узкие места — botte neck problem, <econ.> bottleneck problem


    задача нескольких проблем — <astr.> many-body problem


    задача нескольких тел — <astr.> many-body problem


    задача о смеси бензинов — gasolene blending problem, <econ.> gasoline blending problem, petrol blending problem


    задача о собственных значениях — eigenvalue problem


    задача о составлении пар — matching problem


    задача о четвертой точке — three-point problem


    задача с начальными условиями — initial-value problem


    задача с подвижной границей — moving boundary problem, moving-boundary problem


    задача с узким местом — <econ.> bottleneck problem


    задача четырех красок — four-color problem


    учебная задача с решением — worked problem

    Русско-английский технический словарь > задача

  • 15 задача об оптимальных назначениях

    Универсальный русско-английский словарь > задача об оптимальных назначениях

  • 16 линейное программирование

    1. linear programming

     

    линейное программирование
    —
    [ http://www.iks-media.ru/glossary/index.html?glossid=2400324]

    линейное программирование
    Область математического программирования, посвященная теории и методам решения экстремальных задач, характеризующихся линейной зависимостью между переменными. В самом общем виде задачу Л.п. можно записать так. Даны ограничения типа или в так называемой канонической форме, к которой можно привести все три указанных случая Требуется найти неотрицательные числа xj (j = 1, 2, …, n), которые минимизируют (или максимизируют) линейную форму Неотрицательность искомых чисел записывается так: Таким образом, здесь представлена общая задача математического программирования с теми оговорками, что как ограничения, так и целевая функция — линейные, а искомые переменные — неотрицательны. Обозначения можно трактовать следующим образом: bi — количество ресурса вида i; m — количество видов этих ресурсов; aij — норма расхода ресурса вида i на единицу продукции вида j; xj — количество продукции вида j, причем таких видов — n; cj — доход (или другой выигрыш) от единицы этой продукции, а в случае задачи на минимум — затраты на единицу продукции; нумерация ресурсов разделена на три части: от 1 до m1, от m1 + 1 до m2 и от m2 + 1 до m в зависимости от того, какие ставятся ограничения на расходование этих ресурсов; в первом случае — «не больше», во втором — «столько же», в третьем — «не меньше»; Z — в случае максимизации, например, объем продукции или дохода, в случае же минимизации — себестоимость, расход сырья и т.п. Добавим еще одно обозначение, оно появится несколько ниже; vi — оптимальная оценка i-го ресурса. Слово «программирование» объясняется здесь тем, что неизвестные переменные, которые отыскиваются в процессе решения задачи, обычно в совокупности определяют программу (план) работы некоторого экономического объекта. Слово, «линейное» отражает факт линейной зависимости между переменными. При этом, как указано, задача обязательно имеет экстремальный характер, т.е. состоит в отыскании экстремума (максимума или минимума) целевой функции. Следует с самого начала предупредить: предпосылка линейности, когда в реальной экономике подавляющее большинство зависимостей носит более сложный нелинейный характер, есть огрубление, упрощение действительности. В некоторых случаях оно достаточно реалистично, в других же выводы, получаемые с помощью решения задач Л.п. оказываются весьма несовершенными. Рассмотрим две задачи Л.п. — на максимум и на минимум — на упрощенных примерах. Предположим, требуется разработать план производства двух видов продукции (объем первого — x1; второго — x2) с наиболее выгодным использованием трех видов ресурсов (наилучшим в смысле максимума общей прибыли от реализации плана). Условия задачи можно записать в виде таблицы (матрицы). Исходя из норм, зафиксированных в таблице, запишем неравенства (ограничения): a11x1 + a12x2 ? bi a21x1 + a22x2 ? b2 a31x1 + a32x2 ? b3 Это означает, что общий расход каждого из трех видов ресурсов не может быть больше его наличия. Поскольку выпуск продукции не может быть отрицательным, добавим еще два ограничения: x1? 0, x2? 0. Требуется найти такие значения x1 и x2, при которых общая сумма прибыли, т.е. величина c1 x1 + c2 x2 будет наибольшей, или короче: Удобно показать условия задачи на графике (рис. Л.2). Рис. Л.2 Линейное программирование, I (штриховкой окантована область допустимых решений) Любая точка здесь, обозначаемая координатами x1 и x2, составляет вариант искомого плана. Очевидно, что, например, все точки, находящиеся в области, ограниченной осями координат и прямой AA, удовлетворяют тому условию, что не может быть израсходовано первого ресурса больше, чем его у нас имеется в наличии (в случае, если точка находится на самой прямой, ресурс используется полностью). Если то же рассуждение отнести к остальным ограничениям, то станет ясно, что всем условиям задачи удовлетворяет любая точка, находящаяся в пределах области, края которой заштрихованы, — она называется областью допустимых решений (или областью допустимых значений, допустимым множеством). Остается найти ту из них, которая даст наибольшую прибыль, т.е. максимум целевой функции. Выбрав произвольно прямую c1x1 + c2x2 = П и обозначив ее MM, находим на чертеже все точки (варианты планов), где прибыль одинакова при любом сочетании x1 и x2 (см. Линия уровня). Перемещая эту линию параллельно ее исходному положению, найдем точку, которая в наибольшей мере удалена от начала координат, однако не вышла за пределы области допустимых значений. (Перемещая линию уровня еще дальше, уже выходим из нее и, следовательно, нарушаем ограничения задачи). Точка M0 и будет искомым оптимальным планом. Она находится в одной из вершин многоугольника. Может быть и такой случай, когда линия уровня совпадает с одной из прямых, ограничивающих область допустимых значений, тогда оптимальным будет любой план, находящийся на соответствующем отрезке. Координаты точки M0 (т.е. оптимальный план) можно найти, решая совместно уравнения тех прямых, на пересечении которых она находится. Противоположна изложенной другая задача Л.п.: поиск минимума функции при заданных ограничениях. Такая задача возникает, например, когда требуется найти наиболее дешевую смесь некоторых продуктов, содержащих необходимые компоненты (см. Задача о диете). При этом известно содержание каждого компонента в единице исходного продукта — aij, ее себестоимость — cj ; задается потребность в искомых компонентах — bi. Эти данные можно записать в таблице (матрице), сходной с той, которая приведена выше, а затем построить уравнения как ограничений, так и целевой функции. Предыдущая задача решалась графически. Рассуждая аналогично, можно построить график (рис. Л.3), каждая точка которого — вариант искомого плана: сочетания разных количеств продуктов x1 и x2. Рис.Л.3 Линейное программирование, II Область допустимых решений здесь ничем сверху не ограничена: нужное количество заданных компонентов тем легче получить, чем больше исходных продуктов. Но требуется найти наиболее выгодное их сочетание. Пунктирные линии, как и в предыдущем примере, — линии уровня. Здесь они соединяют планы, при которых себестоимость смесей исходных продуктов одинакова. Линия, соответствующая наименьшему ее значению при заданных требованиях, — линия MM. Искомый оптимальный план — в точке M0. Приведенные крайне упрощенные примеры демонстрируют основные особенности задачи Л.п. Реальные задачи, насчитывающие много переменных, нельзя изобразить на плоскости — для их геометрической интерпретации используются абстрактные многомерные пространства. При этом допустимое решение задачи — точка в n-мерном пространстве, множество всех допустимых решений — выпуклое множество в этом пространстве (выпуклый многогранник). Задачи Л.п., в которых нормативы (или коэффициенты), объемы ресурсов («константы ограничений«) или коэффициенты целевой функции содержат случайные элементы, называются задачами линейного стохастического программирования; когда же одна или несколько независимых переменных могут принимать только целочисленные значения, то перед нами задача линейного целочисленного программирования. В экономике широко применяются линейно-программные методы решения задач размещения производства (см. Транспортная задача), расчета рационов для скота (см. Задача диеты), наилучшего использования материалов (см. Задача о раскрое), распределения ресурсов по работам, которые надо выполнять (см. Распределительная задача) и т.д. Разработан целый ряд вычислительных приемов, позволяющих решать на ЭВМ задачи линейного программирования, насчитывающие сотни и тысячи переменных, неравенств и уравнений. Среди них наибольшее распространение приобрели методы последовательного улучшения допустимого решения (см. Симплексный метод, Базисное решение), а также декомпозиционные методы решения крупноразмерных задач, методы динамического программирования и др. Сама разработка и исследование таких методов — развитая область вычислительной математики. Один из видов решения имеет особое значение для экономической интерпретации задачи Л.п. Он связан с тем, что каждой прямой задаче Л.п. соответствует другая, симметричная ей двойственная задача (подробнее см. также Двойственность в линейном программировании). Если в качестве прямой принять задачу максимизации выпуска продукции (или объема реализации, прибыли и т.д.), то двойственная задача заключается, наоборот, в нахождении таких оценок ресурсов, которые минимизируют затраты. В случае оптимального решения ее целевая функция — сумма произведений оценки (цены) vi каждого ресурса на его количество bi— то есть равна целевой функции прямой задачи. Эта цена называется объективно обусловленной, или оптимальной оценкой, или разрешающим множителем. Основополагающий принцип Л.п. состоит в том, что в оптимальном плане и при оптимальных оценках всех ресурсов затраты и результаты равны. Оценки двойственной задачи обладают замечательными свойствами: они показывают, насколько возрастет (или уменьшится) целевая функция прямой задачи при увеличении (или уменьшении) запаса соответствующего вида ресурсов на единицу. В частности, чем больше в нашем распоряжении данного ресурса по сравнению с потребностью в нем, тем ниже будет оценка, и наоборот. Не решая прямую задачу, по оценкам ресурсов, полученных в двойственной задаче, можно найти оптимальный план: в него войдут все технологические способы, которые оправдывают затраты, исчисленные в этих оценках (см. Объективно обусловленные (оптимальные) оценки). Первооткрыватель Л.п. — советский ученый, академик, лауреат Ленинской, Государственной и Нобелевской премий Л.В.Канторович. В 1939 г. он решил математически несколько задач: о наилучшей загрузке машин, о раскрое материалов с наименьшими расходами, о распределении грузов по нескольким видам транспорта и др., при этом разработав универсальный метод решения этих задач, а также различные алгоритмы, реализующие его. Л.В.Канторович впервые точно сформулировал такие важные и теперь широко принятые экономико-математические понятия, как оптимальность плана, оптимальное распределение ресурсов, объективно обусловленные (оптимальные) оценки, указав многочисленные области экономики, где могут быть применены экономико-математические методы принятия оптимальных решений. Позднее, в 40—50-х годах, многое сделали в этой области американские ученые — экономист Т.Купманс и математик Дж. Данциг. Последнему принадлежит термин «линейное программирование». См. также: Ассортиментные задачи, Базисное решение, Блочное программирование, Булево линейное программирование, Ведущий столбец, Ведущая строка, Вершина допустимого многогранника, Вырожденная задача, Гомори способ, Граничная точка, Двойственная задача, Двойственность в линейном программировании, Дифференциальные ренты, Дополняющая нежесткость, Жесткость и нежесткость ограничений ЛП, Задача диеты, Задача о назначениях, Задача о раскрое, Задачи размещения, Исходные уравнения, Куна — Таккера условия, Множители Лагранжа, Область допустимых решений, Опорная прямая, Распределительные задачи, Седловая точка, Симплексная таблица, Симплексный метод, Транспортная задача.
    [ http://slovar-lopatnikov.ru/]

    Тематики

    EN

    Русско-английский словарь нормативно-технической терминологии > линейное программирование

  • 17 распределительные задачи

    1. allocation problems

     

    распределительные задачи
    Класс экономико-математических задач, связанных с распределением ресурсов по работам, которые необходимо выполнить. Если ресурсов достаточно, чтобы каждую работу выполнить наиболее эффективно, задача не возникает. В обратном же случае переброска, передача ресурсов с одной работы на другую приводит к изменению общей эффективности всех работ вместе взятых. Поэтому Р.з. заключается в отыскании наилучшего распределения ресурсов, при котором либо максимизируется общий доход или результат, выраженный в какой-либо другой форме, либо минимизируются затраты. Такие задачи чаще всего приводятся к линейному виду (иногда искусственно за счет упрощений) и решаются методом линейного программирования. Если через xij обозначить объем ресурса i, то математическая формулировка Р.з. такова: найти минимум или максимум целевой функции (минимум затрат или максимум эффекта) при ограничениях по объему ресурсов и потребности в них. При этом различаются два вида таких задач: а) сбалансированная (закрытая) — если общий объем ресурсов равен общей потребности в них ; б) несбалансированная (открытая), когда ? и требуется не только распределить ресурсы по работам (потребителям), но также решить, какие работы не следует выполнять (т.е. каких потребителей не удовлетворять), если ресурсы меньше потребностей, либо какие ресурсы не использовать — в противоположном случае. К Р.з. относятся такие широко распространенные задачи, как транспортная задача линейного программирования, задача о назначениях и многие другие. Задачи распределения могут решаться в статической (однократной) и в динамической постановке. В последнем случае часто применяют методы стохастического программирования (в которых принятие решений основано на вероятностных оценках будущих значений параметров).
    [ http://slovar-lopatnikov.ru/]

    Тематики

    EN

    Русско-английский словарь нормативно-технической терминологии > распределительные задачи

  • 18 дискретное программирование

    1. discrete programming

     

    дискретное программирование
    Раздел оптимального программирования, изучающий экстремальные задачи, в которых на искомые переменные накладывается условие целочисленности, а область допустимых решений конечна. Таким образом, здесь используется модель общей задачи математического программирования с дополнительным ограничением: x1, x2, …, xn — целочисленны. В экономике огромное количество задач носит дискретный характер. Прежде всего это связано с физической неделимостью многих факторов и объектов расчета: например, нельзя построить 2,3 завода или купить 1,5 автомобиля. Все отраслевые задачи строятся в расчете на определенное количество предприятий или проектных вариантов. В планировании распространены типовые размеры предприятий, типовые мощности агрегатов — все это вносит дискретность в расчеты. Наконец, упомянем плановые показатели: годовые, месячные или суточные периоды — это дискретные, раздельные периоды, у каждого из которых есть свое начало и свой конец. Дискретными являются задача о коммивояжере, задача о назначениях, задачи теории расписаний и другие. Для решения задач Д.п. применяется ряд способов. Самый простой — решение обычной задачи линейного программирования с проверкой полученного результата на целочисленность и округлением его до приближенного целочисленного решения. Скажем, получилось из расчета, что надо построить 2,3 завода, выбираются либо два, либо три (что, разумеется, требует дополнительного анализа), точно так же не 1,5 автомобиля, а два или один. Часто в практических задачах искомые переменные принимают только два значения — единицу и нуль. (Их называют задачами булева линейного программирования.) Это означает, что данный вариант решения принимается или отвергается (строить или не строить шахту, приобретать или не приобретать машину и т.п.). Иногда Д.п. называется целочисленным. Как видно из приведенных примеров, это не лишено основания, хотя некоторые математики считают такой термин неправильным (исходя из того, что, строго говоря, дискретное — это не обязательно целочисленное, например, ряд чисел — 1,1 — 1,2 — 1,3… — дискретный, но не целочисленный). Поэтому правильнее, очевидно, считать целочисленное программирование частным случаем дискретного.
    [ http://slovar-lopatnikov.ru/]

    Тематики

    EN

    Русско-английский словарь нормативно-технической терминологии > дискретное программирование

  • 19 назначение

    n. purpose, assignment, appointment; задача о назначениях, assignment problem

    Русско-английский словарь математических терминов > назначение

  • 20 назначение


    * * *

    n. purpose, assignment, appointment;

    задача о назначениях - assignment problem

    Русско-английский математический словарь > назначение

Страницы
  • 1
  • 2

См. также в других словарях:

  • Задача О Назначениях — задача об оптимальном распределении ряда работ между исполнителями при условии взаимного соответствия между множествами работ и исполнителей. Словарь бизнес терминов. Академик.ру. 2001 …   Словарь бизнес-терминов

  • Задача о назначениях — [assignment problem] вид задачи  линейного программирования, с помощью которой решаются вопросы типа: как распределить рабочих по станкам, чтобы общая выработка была наибольшей или затраты на заработную плату наименьшими (поскольку для каждой… …   Экономико-математический словарь

  • Задача о назначениях — [assignment problem] вид задачи  линейного программирования, с помощью которой решаются вопросы типа: как распределить рабочих по станкам, чтобы общая выработка была наибольшей или затраты на заработную плату наименьшими (поскольку для каждой… …   Экономико-математический словарь

  • задача о назначениях — Вид задачи линейного программирования, с помощью которой решаются вопросы типа: как распределить рабочих по станкам, чтобы общая выработка была наибольшей или затраты на заработную плату наименьшими (поскольку для каждой комбинации «рабочий… …   Справочник технического переводчика

  • ЗАДАЧА О НАЗНАЧЕНИЯХ — задача о наилучшем распределении некоторого числа работ между таким же числом исполнителей при условии взаимно однозначного соответствия между множествами работ и исполнителем. З.о н. представляет собой частный случай транспортной задачи.… …   Большой экономический словарь

  • ЗАДАЧА О НАЗНАЧЕНИЯХ — (ASSIGNMENT PROBLEM) задача о наилучшем распределении некоторого числа работ между таким же числом исполнителей при условии взаимно однозначного соответствия между мн вами работ и исполнителей. При ее решении ищут оптим. назначение из условия… …   Глоссарий терминов по грузоперевозкам, логистике, таможенному оформлению

  • Линейное программирование — [linear programming] область математического программирования, посвященная теории и методам решения экстремальных задач, характеризующихся линейной зависимостью между переменными. В самом общем виде задачу Л.п. можно записать так. Даны… …   Экономико-математический словарь

  • Линейное программирование — [linear programming] область математического программирования, посвященная теории и методам решения экстремальных задач, характеризующихся линейной зависимостью между переменными. В самом общем виде задачу Л.п. можно записать так. Даны… …   Экономико-математический словарь

  • линейное программирование — — [http://www.iks media.ru/glossary/index.html?glossid=2400324] линейное программирование Область математического программирования, посвященная теории и методам решения экстремальных задач, характеризующихся линейной зависимостью между… …   Справочник технического переводчика

  • З — Забалансовое финансирование (Оff balance sheet finance) Забалансовые счета (Оff balance accounts) Зависимая компания (предприятие) (affiliated company) …   Экономико-математический словарь

  • Муравьиный алгоритм — Поведение муравьёв явилось вдохновением для создания метаэвристической технологии оптимизации Муравьиный алгоритм (алгоритм оптимизации подражанием муравьиной колонии, англ. ant colony optimization, ACO)  од …   Википедия

Поделиться ссылкой на выделенное

Прямая ссылка:
… Нажмите правой клавишей мыши и выберите «Копировать ссылку»